// #include <stdio.h>
// #include <stdlib.h>
// #include <Windows.h>
// #include <stdbool.h>
//
// typedef int ElemType;
// // 节点结构
// typedef struct Node {
//     ElemType data;
//     struct Node* next;
// } Node;
//
// // 链表结构
// typedef struct LinkedList {
//     Node* head;  // 头结点
// } LinkedList;
//
// // 创建链表并初始化
// LinkedList* create_list() {
//     LinkedList* list = (LinkedList*)malloc(sizeof(LinkedList));
//     if (list == NULL) {
//         printf("内存分配失败\n");
//         exit(1);
//     }
//     list->head = (Node*)malloc(sizeof(Node)); // 创建头结点
//     if (list->head == NULL) {
//         printf("内存分配失败\n");
//         free(list);
//         exit(1);
//     }
//     list->head->next = NULL;  // 初始化头结点的下一个指针
//     return list;
// }
//
// // 判断链表是否为空
// int is_empty(LinkedList* list) {
//     return list->head->next == NULL;
// }
//
// // 尾插法插入
// void insert_at_tail(LinkedList* list, ElemType data) {
//     Node* new_node = (Node*)malloc(sizeof(Node));
//     if (new_node == NULL) {
//         printf("内存分配失败\n");
//         exit(1);
//     }
//     new_node->data = data;
//     new_node->next = NULL;
//
//     Node* current = list->head;
//     while (current->next != NULL) {
//         current = current->next;
//     }
//     current->next = new_node;
// }
//
// // 显示链表内容
// void display(LinkedList* list) {
//     Node* current = list->head->next;
//     printf("链表内容: ");
//     while (current != NULL) {
//         printf("%d ", current->data);
//         current = current->next;
//     }
//     printf("\n");
// }
//
// // 释放链表内存
// void free_list(LinkedList* list) {
//     Node* current = list->head;
//     while (current != NULL) {
//         Node* next_node = current->next;
//         free(current);
//         current = next_node;
//     }
//     free(list);
// }
//
// // 将链表按a1,an,a2,an-1,a3,an-2的顺序重新排列，空间复杂度O(1)
// void rearrange_list(LinkedList* L) {
//     if (L == NULL || L->head == NULL || L->head->next == NULL || L->head->next->next == NULL) {
//         return; // 空链表或只有一个节点或两个节点，无需处理
//     }
//
//     // 1. 使用快慢指针找到链表中点
//     Node* slow = L->head->next;
//     Node* fast = L->head->next;
//
//     while (fast->next != NULL && fast->next->next != NULL) {
//         slow = slow->next;
//         fast = fast->next->next;
//     }
//
//     // 2. 将链表分为两部分
//     Node* second_half = slow->next;
//     slow->next = NULL; // 切断链表
//
//     // 3. 反转后半部分链表
//     Node* prev = NULL;
//     Node* current = second_half;
//     Node* next_node = NULL;
//
//     while (current != NULL) {
//         next_node = current->next;
//         current->next = prev;
//         prev = current;
//         current = next_node;
//     }
//     second_half = prev; // 反转后的链表头
//
//     // 4. 合并两个链表
//     Node* first = L->head->next;
//     Node* second = second_half;
//
//     while (second != NULL) {
//         Node* first_next = first->next;
//         Node* second_next = second->next;
//
//         first->next = second;
//         second->next = first_next;
//
//         first = first_next;
//         second = second_next;
//     }
// }
//
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//     LinkedList* L = create_list();
//     insert_at_tail(L, 10);
//     insert_at_tail(L, 20);
//     insert_at_tail(L, 30);
//     insert_at_tail(L, 40);
//     insert_at_tail(L, 50);
//     insert_at_tail(L, 60);
//
//     printf("原始链表: ");
//     display(L);
//
//     rearrange_list(L);
//
//     printf("重新排列后链表: ");
//     display(L);
//
//     free_list(L);
//     return 0;
// }